/**
 * 最优性能
 * 主要思路也是先把数据转成Map去存储，之后遍历的同时借助对象的引用，直接从Map找对应的数据做存储。
 * 不同点在遍历的时候即做Map存储,有找对应关系。性能会更好
 */
function arrayToTree(items) {
  const result = []; // 存放结果集
  const itemMap = {}; //
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: []
      };
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    };

    const treeItem = itemMap[id];

    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: []
        };
      }
      itemMap[pid].children.push(treeItem);
    }
  }
  return result;
}

/** 扁平数据结构转Tree */
const arr = [
  { id: 1, name: '部门1', pid: 0 },
  { id: 2, name: '部门2', pid: 1 },
  { id: 3, name: '部门3', pid: 1 },
  { id: 4, name: '部门4', pid: 3 },
  { id: 5, name: '部门5', pid: 4 }
];

console.log(arrayToTree(arr));

const flatToTree = arr => {
  const map = new Map();
  const root = [];
  let item;
  while ((item = arr.shift())) {
    const self = { ...item, children: [] };
    if (map.has(item.pid)) map.get(item.pid).children.push(self);
    else root.push(self);
    map.set(item.id, self);
  }
  return root;
};

console.log(flatToTree(arr));
